
// Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#include <queue>
#include <utility>
using namespace std;
class CBTInserter
{
public:
    // 层状遍历初始化待插入队列
    void init_que(TreeNode *_root)
    {
        if (!_root)
            return;
        queue<TreeNode *> _que;
        _que.push(_root);
        while (!_que.empty())
        {
            TreeNode *node = _que.front();
            _que.pop();
            if (node->left)
                _que.push(node->left);
            else
                que.push({&(node->left), node->val});
            if (node->right)
                _que.push(node->right);
            else
                que.push({&(node->right), node->val});
        }
    }
    CBTInserter(TreeNode *_root)
    {
        root = _root;
        init_que(_root);
    }
    // 从队列里取插入位置 然后自己的左右入队列
    int insert(int v)
    {
        TreeNode *new_node = new TreeNode(v);
        auto father = que.front();
        que.pop();
        *(father.first) = new_node;
        que.push({&(new_node->left), new_node->val});
        que.push({&(new_node->right), new_node->val});
        return father.second;
    }

    TreeNode *get_root()
    {
        return root;
    }
    TreeNode *root;
    queue<pair<TreeNode **, int>> que;
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(v);
 * TreeNode* param_2 = obj->get_root();
 */